package depth_first_search;

/**
 * author :  apurv verma
 * email  :  dapurv5@gmail.com
 */

import java.util.Comparator;
import java.util.PriorityQueue;


public class DepthFirstSearch3D {
	
	private Maze3D maze3d;
	Dimension path[];
	Dimension shortestPath[];
	boolean isVisited3D[][][];
	boolean pathFound=false;
	Comparator<Dimension> comparator;
	
		
	/*
	 * CONSTRUCTOR FOR INITIALIZING maze3d.
	 */
	public DepthFirstSearch3D(Maze3D maze){
		maze3d=maze;
		int n=maze3d.n;
		path=new Dimension[n*n*n];
		isVisited3D=new boolean[n][n][n];
		comparator=(Comparator<Dimension>) new CellComparator(new Dimension(maze.goalLoc.getX(),maze.goalLoc.getY(),maze.goalLoc.getZ())); // A comparator for comparing cells.
	}
	
	
													//3D MAZE
	
	
	/*
	 * FUNCTION TO SEARCH THE SHORTEST PATH IN A 3D MAZE.
	 */
	public void doSearchOn3DMaze(){
		path[0]=maze3d.startLoc;
		isVisited3D[maze3d.startLoc.getX()][maze3d.startLoc.getY()][maze3d.startLoc.getZ()]=true;
		DFS3D(maze3d.startLoc,1);
	}
	
	
	/*
	 *HELPER FUNCTION FOR THE FUNCTION doSearchOn3DMaze(). 
	 */
	public void DFS3D(Dimension u,int i){

		if(pathFound)
			return;
		

		//THE CURRENT CELL u HAS BEEN VISITED WITH THIS RECURSIVE CALL
		isVisited3D[u.getX()][u.getY()][u.getZ()]=true;
		
		//CONSTRUCT A PRIORITYQUEUE INSTEAD OF A STACK TO STORE ALL POSSIBLE VALID MOVES FROM THE CURRENT CELL u.
		//Stack<Dimension> s=new Stack<Dimension>();
		PriorityQueue<Dimension> pq=new PriorityQueue<Dimension>(6,comparator);
		
		//CHECK WHETHER THE GOAL CELL HAS BEEN REACHED.
		int a=u.getX();
		int b=u.getY();
		int c=u.getZ();
		if(a==maze3d.goalLoc.getX() && b==maze3d.goalLoc.getY() && c==maze3d.goalLoc.getZ()){
			//System.out.println("a path found");
			displayPath3D(i);		
			pathFound=true;
		}
		
		//FIND VALID MOVES FROM THE CURRENT CELL AND PUSH THEM INTO THE PRIORITY QUEUE.
		if(a-1>=0 && maze3d.maze[a-1][b][c]==maze3d.VALID_CELL && !isVisited3D[a-1][b][c]){
			pq.offer(new Dimension(a-1,b,c));
		}
		if(a+1<maze3d.n && maze3d.maze[a+1][b][c]==maze3d.VALID_CELL && !isVisited3D[a+1][b][c]){
			pq.offer(new Dimension(a+1,b,c));
		}
		if(b-1>=0 && maze3d.maze[a][b-1][c]==maze3d.VALID_CELL && !isVisited3D[a][b-1][c]){
			pq.offer(new Dimension(a,b-1,c));
		}
		if(b+1<maze3d.n && maze3d.maze[a][b+1][c]==maze3d.VALID_CELL && !isVisited3D[a][b+1][c]){
			pq.offer(new Dimension(a,b+1,c));
		}
		if(c-1>=0 && maze3d.maze[a][b][c-1]==maze3d.VALID_CELL && !isVisited3D[a][b][c-1]){
			pq.offer(new Dimension(a,b,c-1));
		}
		if(c+1<maze3d.n && maze3d.maze[a][b][c+1]==maze3d.VALID_CELL && !isVisited3D[a][b][c+1]){
			pq.offer(new Dimension(a,b,c+1));
		}
		while(!pq.isEmpty()){
			Dimension v=(Dimension) pq.poll();
			path[i]=v;
			DFS3D(v,i+1);
			
		}
		
		//WHEN RETURNING FROM THE CELL, REMEMBER TO NEGATE THE isVisited FLAG FOR THAT CELL.
		isVisited3D[u.getX()][u.getY()][u.getZ()]=false;
	}
	
	/*
	 * DISPLAY THE PATH IN THE 3D MAZE AND STORE THE RESULT IN shortestPath.
	 */
	public void displayPath3D(int depth){
		int k=0;
		shortestPath=new Dimension[depth];
		System.out.println(path[k].getX()+" , "+path[k].getY()+" , "+path[k].getZ());
		shortestPath[k]=new Dimension(path[k].getX(),path[k].getY(),path[k].getZ());
		k++;
		while(k<depth){
			System.out.println(path[k].getX()+" , "+path[k].getY()+" , "+path[k].getZ());
			shortestPath[k]=new Dimension(path[k].getX(),path[k].getY(),path[k].getZ());
			k+=1;
		}
	}
	
}
